from collections import deque

#
# class Node(object):
#
#     """节点类"""
#     def __init__(self, intent, elem, lchild=None, rchild=None):
#         self.intent = intent
#         self.elem = elem
#         self.lchild = lchild
#         self.rchild = rchild
#     def __str__(self):
#         return "意图是：%s" % (self.intent)

class Tree(object):
    """树类"""
    def __init__(self,intent,  lchild=None, rchild=None):
        # self.root = root
        self.intent = intent
        # self.elem = elem
        self.lchild = lchild
        self.rchild = rchild

    # def add(self, item, elem):
    #     node = Node(item, elem)  # 将Node类实例化参数node
    #     if self.root is None:
    #         self.root = node
    #         return
    #     queue = [self.root]  # 创建一个队列，将根节点放入队列中
    #     while queue:
    #         cur_node = queue.pop(0)  # 向队列queue中取出第一个节点进行判断
    #         if cur_node.lchild is None:
    #             cur_node.lchild = node
    #             return
    #         else:
    #             queue.append(cur_node.lchild)
    #         if cur_node.rchild is None:
    #             cur_node.rchild = node
    #             return
    #         else:
    #             queue.append(cur_node.rchild)
    # def  breadth(self):
    #
    #     if self.root is None:  #首先判断根节点是否为空，为空则返回
    #         return
    #     queue=[self.root]#将根节点放入队列中
    #     while queue:
    #         cur_node = queue.pop(0)#取出节点
    #         print(cur_node.elem,end=' ')#打印节点值，也是广度遍历的值
    #         if cur_node.lchild is not None:#判断左子树
    #             queue.append(cur_node.lchild)
    #         if cur_node.rchild is not None:#判断右子树
    #             queue.append(cur_node.rchild)

#
# def bfs(self):
#     ret = []
#     queue = deque([self.root])
#     while queue:
#         node = queue.popleft()
#         if node:
#             ret.append(node.intent)
#             queue.append(node.lchild)
#             queue.append(node.rchild)
#     return ret

    """先序遍历"""

def preorder(root):
    if root == None:
        return
    print(root.intent, end=',')
    preorder(root.lchild)
    preorder(root.rchild)
    '列表创建二叉树'
def listcreattree(root, llist, i):  ###用列表递归创建二叉树，
  # 它其实创建过程也是从根开始a开始，创左子树b，再创b的左子树，如果b的左子树为空，返回none。
 # 再接着创建b的右子树，
    if i < len(llist):
        if llist[i] == None:
            return None
    else:
        root = Tree(llist[i])
      # 往左递推
        root.lchild = listcreattree(root.lchild, llist, 2 * i + 1)  # 从根开始一直到最左，直至为空，
         # 往右回溯
        root.rchild = listcreattree(root.rchild, llist, 2 * i + 2)  # 再返回上一个根，回溯右，
         # 再返回根'
        return root  ###这里的return很重要
    return root

    # def pre(self,root):
    #     if not root:
    #         return None
    #     print(root.intent,end='\t')
    #     self.pre(self,root.lchild)
    #     self.pre(self,root.rchild)
    #


    # """列表转化为二叉树"""
    # def construct_list_tree(self, values=None, list=None):
    #     if not values:
    #         return None
    #     self.root = Node(values[0],list[0])
    #     queue = deque([self.root])
    #     leng = len(values)
    #     nums = 1
    #     while nums < leng:
    #         node = queue.popleft()
    #         if node:
    #             node.left = Node(values[nums],list[nums]) if values[nums] else None
    #             queue.append(node.left)
    #             if nums + 1 < leng:
    #                 node.right = Node(values[nums + 1], list[nums+1]) if values[nums + 1] else None
    #                 queue.append(node.right)
    #                 nums += 1
    #             nums += 1
if __name__== '__main__':

    list = [1,2,3,None,None,4,5]
    # tree.construct_list_tree(list,list)
    t=listcreattree(None,list,0)
    # tree.breadth()

    preorder(t)